package com.leetcode.hot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: com.leetcode.hot100
 * @Author: lei
 * @CreateTime: 2024-03-13  22:51
 * @Description: TODO
 * @Version: 1.0
 */
public class 合并区间_56 {
    public static void main(String[] args) {
        //int[][] intervals = {{1, 4}, {2, 3}};
        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        System.out.println(Arrays.deepToString(merge(intervals)));
    }


    public static int[][] merge(int[][] intervals) {
        // 针对二维数组中的每一个小数组进行排序，确保小数组的开始元素<=结尾元素
        for (int[] interval : intervals) {
            Arrays.sort(interval);
        }
        // 针对二维数组的元素排序，确保每个小数组都是有序的
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
        ArrayList<int[]> arrayList = new ArrayList<>();
        int index = 0;
        arrayList.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int[] current = intervals[i];
            int[] peek = arrayList.get(index);
            if (current[0] > peek[1]) {
                arrayList.add(current);
                index += 1;
            } else {
                peek[1] = Math.max(peek[1], current[1]);
            }
        }

        return arrayList.toArray(new int[arrayList.size()][]);
    }
}


